from platform import node
import random
from typing import *
from math import inf


class Node:

    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.mid = ((r - l) >> 1) + l
        self.left = None
        self.right = None
        self.vals = []
        self.mn_val = inf

    def Left(self):
        if self.left == None:
            self.left = Node(self.l, self.mid)
        return self.left

    def Right(self):
        if self.right == None:
            self.right = Node(self.mid + 1, self.r)
        return self.right


class SegmentTree:

    def __init__(self, mx: int) -> None:
        self.mx = mx
        self.root = Node(1, mx)

    def add(self, index: int, val: int) -> None:
        self.__add(self.root, index, val)

    def query(self, index: int) -> int:
        return self.__query(self.root, index, self.mx)

    def remove(self, index: int):
        return self.__remove(self.root, index)

    def __query(self, p: Node, l: int, r: int):
        if l <= p.l and p.r <= r:
            return p.mn_val
        ans = inf
        if l <= p.mid:
            ans = self.__query(p.Left(), l, min(p.mid, r))
        if r > p.mid:
            ans = min(ans, self.__query(p.Right(), max(p.mid + 1, l), r))
        return ans

    def __add(self, p: Node, index: int, val: int):
        if p.l == p.r and p.l == index:
            p.vals.append(val)
            p.mn_val = p.vals[0]
            return
        elif index <= p.mid:
            self.__add(p.Left(), index, val)
        else:
            self.__add(p.Right(), index, val)
        p.mn_val = min(p.Left().mn_val, p.Right().mn_val)

    def __remove(self, p: Node, index: int):
        if p.l == p.r and p.l == index:
            p.vals.pop(0)
            p.mn_val = p.vals[0] if p.vals else inf
            return
        elif index <= p.mid:
            self.__remove(p.Left(), index)
        else:
            self.__remove(p.Right(), index)
        p.mn_val = min(p.Left().mn_val, p.Right().mn_val)


class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        mx, n = max(baskets), len(fruits)
        st = SegmentTree(mx)
        for i, v in enumerate(baskets):
            st.add(v, i)

        ans = 0
        for v in fruits:
            id = st.query(v)
            if id < n:
                st.remove(baskets[id])
            else:
                ans += 1
        return ans


# 除法错写成乘法
# 赋值错写成判等
# 开点的范围一端未做聚合判断

s = Solution()
print(s.numOfUnplacedFruits(fruits=[4, 2, 5], baskets=[3, 5, 4]))
print(s.numOfUnplacedFruits(fruits=[3, 6, 1], baskets=[6, 4, 7]))


a = []
b = []
for _ in range(100):
    a.append(random.randint(1, 100))
    b.append(random.randint(1, 100))

f = open("1.txt", "w")
print(a, file=f)
f = open("1.txt", "a")
print(b, file=f)
